package stack;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Stack;
import java.util.stream.Collectors;

/**
 * @author huangxin
 * @date 2019/6/22-17:48
 */
public class PolandNotation {
    public static void main(String[] args) {
        //中缀表达式转后缀表达式
        // 1+((2+3)*4)-5 => 1 2 3 + 4 * + 5 -
        String expression = "1+((2+3)*4)-5";

        List<String> list = toInfixExpressionList(expression);
        //中缀表达式转后缀表达式
        List<String> suffixExpression2 = parseSuffixExpressionList(list);
        int calculate = calculate(suffixExpression2);
        System.out.printf("后缀表达式 %s的结果为 %d\n", suffixExpression2, calculate);


        //逆波兰表达式
        //(3+4)*5-6 =>  3 4 + 5 * 6 - = 29
//        String suffixExpression = "3 4 + 5 * 6 -";
//
//        List<String> listString = getListString(suffixExpression, " ");
//
//
//        int result = calculate(listString);
//        System.out.printf("后缀表达式 %s = %d\n", suffixExpression, result);
    }

    /**
     * 中缀转后缀
     * * 具体步骤如下:
     * * 1初始化两个栈：运算符栈s1和储存中间结果的栈s2；
     * * 2从左至右扫描中缀表达式；
     * * 3遇到操作数时，将其压s2；
     * * 4遇到运算符时，比较其与s1栈顶运算符的优先级：
     * * 如果s1为空，或栈顶运算符为左括号“(”，则直接将此运算符入栈；
     * * 否则，若优先级比栈顶运算符的高，也将运算符压入s1；
     * * 否则，将s1栈顶的运算符弹出并压入到s2中，再次转到(4-1)与s1中新的栈顶运算符相比较；
     * * 5遇到括号时：
     * * (1) 如果是左括号“(”，则直接压入s1
     * * (2) 如果是右括号“)”，则依次弹出s1栈顶的运算符，并压入s2，直到遇到左括号为止，此时将这一对括号丢弃
     * * 重复步骤2至5，直到表达式的最右边
     * * 将s1中剩余的运算符依次弹出并压入s2
     * * 依次弹出s2中的元素并输出，结果的逆序即为中缀表达式对应的后缀表达式
     *
     * @param list
     * @return
     */
    public static List<String> parseSuffixExpressionList(List<String> list) {
        Stack<String> s1 = new Stack<>();
        //由于s2没有pop操作,所以使用ArrayList
        List<String> s2 = new ArrayList<>();

        for (String item : list) {
            if (item.matches("\\d+")) {
                s2.add(item);
            } else {
                //不为数字
                if (s1.isEmpty() || s1.peek().equals("(") || item.equals("(")) {
                    //s1如果为空或者栈顶为左括号 或者c为左括号,则进栈
                    s1.push(item);
                } else if (item.equals(")")) {
                    //如果为右括号,则依次弹出s1栈顶的运算符，并压入s2，直到遇到左括号为止
                    while (!s1.peek().equals("(")) {
                        s2.add(s1.pop());
                    }
                    s1.pop();//弹出(
                } else {
                    while (true) {
                        //与栈顶的运算符比较优先级
                        if (s1.isEmpty() || priority(item) > priority(s1.peek())) {
                            //优先级比栈顶的高,进栈
                            s1.push(item);
                            break;
                        } else {
                            //将s1栈顶的运算符弹出并压入到s2中，再次与s1中新的栈顶运算符相比较；
                            s2.add(s1.pop());
                        }
                    }
                }
            }
        }
//        将s1中剩余的运算符依次弹出并压入s2
        while (!s1.isEmpty()){
            s2.add(s1.pop());
        }
        return s2;

    }

    /**
     * @param expression
     * @return
     */
    public static List<String> toInfixExpressionList(String expression) {
        //存放中缀表达式
        List<String> list = new ArrayList<>();
        //多位数拼接字符串
        String str = "";
        //指针
        int index = 0;
        //每遍历到一个字符,就放入c
        char c;
        do {
            c = expression.charAt(index);
            if (c < 48 || c > 57) {
                list.add(c + "");
            } else {
                //拼接
                str += c;
                //如果是数字则进栈
                if (index + 1 >= expression.length()) {
                    //如果指针指向最后一个元素
                    list.add(str);
                    break;
                } else {
                    //如果下一个元素不为数字
                    if (expression.charAt(index + 1) < 48 || expression.charAt(index + 1) > 57) {
                        //拼接完成的数字
                        list.add(str);
                        //清空
                        str = "";
                    }
                }
            }
            index++;
        } while (index < expression.length());

        return list;
    }

    //返回运算符的优先级,数字越大,优先级越高
    public static int priority(String oper) {
        if (oper.equals('*') || oper.equals('/')) {
            return 1;
        } else if (oper.equals('+') || oper.equals('-')) {
            return 0;
        } else {
            return -1;
        }
    }

    public static List<String> getListString(String suffixExpression, String regex) {
        return Arrays.asList(suffixExpression.split(regex));
    }


    public static int calculate(List<String> list) {
        Stack<String> stack = new Stack<>();
        for (String item : list) {
            //\\d匹配多位数字
            if (item.matches("\\d+")) {
                stack.push(item);
            } else {
                //pop出两个数
                int num2 = Integer.parseInt(stack.pop());
                int num1 = Integer.parseInt(stack.pop());
                int res = 0;
                if (item.equals("+")) {
                    res = num1 + num2;
                } else if (item.equals("-")) {
                    res = num1 - num2;
                } else if (item.equals("*")) {
                    res = num1 * num2;
                } else if (item.equals("/")) {
                    res = num1 / num2;
                } else {
                    throw new RuntimeException("运算符错误");
                }
                //入栈
                stack.push(res + "");
            }
        }
        //最近留在stack中的数据是运算结果
        return Integer.parseInt(stack.pop());
    }
}
